package dmsxl.lianbiao;

/**
 * Author: Zhang Dongwei
 * Date: 2023/4/7 20:44
 */
public class lb6_07 {

    public static void main(String[] args) {
        ListNode node = new ListNode(4);
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(8);
        ListNode node3 = new ListNode(4);
        ListNode node4 = new ListNode(5);

        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(0);
        ListNode node7 = new ListNode(1);

        node.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;

        node5.next = node6;
        node6.next = node7;
        node7.next = node2;

        ListNode res = getIntersectionNode(node, node5);
//        while (res != null){
//            System.out.println(res.val);
//            res = res.next;
//        }
        System.out.println(res.val);
    }

//    有点问题,超出时间限制
    public static ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        ListNode c1 = headA;
        ListNode c2 = headB;
//        ListNode res = new ListNode(-1);
//        int l1 = 0, l2 = 0;
//        while (c1 != null){
//            l1 ++;
//            c1 = c1.next;
//        }
//        while (c2 != null){
//            l2 ++;
//            c2 = c2.next;
//        }
//        System.out.println(l1);
//        System.out.println(l2);

        while (c1.next != null && c2.next != null){
            c1 = c1.next;
            c2 = c2.next;
            if (c1.next == null) c1 = headB;
            if (c2.next == null) c2 = headA;
            if (c1.next == c2.next) return c1.next;
        }
        return null;
    }

//    看的题解
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode c1 = headA;
        ListNode c2 = headB;
        int l1 = 0, l2 = 0;
        while (c1 != null){
            l1 ++;
            c1 = c1.next;
        }
        while (c2 != null){
            l2 ++;
            c2 = c2.next;
        }
        c1 = headA;
        c2 = headB;
        if (l2 > l1){
            int temLen = l1;
            l1 = l2;
            l2 = temLen;

            ListNode temNode = c1;
            c1 = c2;
            c2 = temNode;
        }
        int gap = l1 - l2;
        while (gap > 0){
            c1 = c1.next;
            gap --;
        }
        while (c1 != null){
            if (c1 == c2){
                return c1;
            }
            c1 = c1.next;
            c2 = c2.next;
        }
        return null;
    }
}
